#define _CRT_SECURE_NO_WARNINGS

//#include <iostream>
//#include <map>
//
//using namespace std;
//
//int main()
//{
//	map<string, char> m;
//
//	// 插入
//	m["one"];
//	// 修改
//	m["one"] = '1';
//	// 插入 + 修改
//	m["two"] = '2';
//	// 查找
//	cout << m["one"] << endl;
//
//	return 0;
//}



//#include <map>
//#include <vector>
//#include <string>
//#include <algorithm>
//
//using namespace std;
//
//int compare(const void* a, const void* b)
//{
//	pair<string, int>* x = (pair<string, int>*)a;
//	pair<string, int>* y = (pair<string, int>*)b;
//
//	return x->second - y->second;
//}
//
//class Solution
//{
//public:
//	vector<string> topKFrequent(vector<string>& words, int k)
//	{
//		map<string, int> m;
//		for (auto it = words.begin(); it < words.end(); it++)
//		{
//			m[*it]++;
//		}
//		vector<pair<string,int>> v(m.begin(), m.end());
//		stable_sort(v.begin(), v.end(), compare);
//		vector<string> ret;
//		for (auto it = v.begin(); it < v.end(); it++)
//		{
//			ret.push_back(it->first);
//		}
//		return ret;
//	}
//};

#include "AVLTree.h"

// 测试代码

void TestAVLTree1()
{
	AVLTree<int, int> t;
	// 常规的测试⽤例
	//int a[] = { 16,3,7,11,9,26,18,14,15 };
	// 特殊的带有双旋场景的测试⽤例

	//int a[] = { 4,2,6,1,3,5,15,7,16,14 };
	int a[] = { 25,15,35,10,20,30,40,5,12,11 };
	for (auto e : a)
	{
		t.Insert({ e, e });
		cout << t.IsBalanceTree(t.GetRoot()) << endl;
	}
	t.InOrder(t.GetRoot());
	cout << endl;
	cout << t.IsBalanceTree(t.GetRoot()) << endl;
}

// 插⼊⼀堆随机值，测试平衡，顺便测试⼀下高度和性能等
void TestAVLTree2()
{
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << "Insert:" << end2 - begin2 << endl;
	cout << "Height:" << t.Height(t.GetRoot()) << endl;
	cout << "Size:" << t.Size(t.GetRoot()) << endl;
	size_t begin1 = clock();

	// 擦除确定在的值
	for (auto it = v.begin(); it < v.begin() + 10; it++)
	{
		t.Erase({ *it,*it });
	}

    // 随机值
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}
	size_t end1 = clock();
	cout << "Find:" << end1 - begin1 << endl;

	cout << "IsBalance:" << t.IsBalanceTree(t.GetRoot()) << endl;

}
int main()
{
	//TestAVLTree1();
	TestAVLTree2();

	return 0;
}
